package 算法.NiuKe.TB;

import 算法.NiuKe.ListNode;

/**
 * @author:谢君臣
 * @Date:2021/5/216:36
 * @version:1.0
 * @function: 对于一个给定的链表，返回环的入口节点，如果没有环，返回null
 */
public class NC2 {
    public static void main(String[] args) {
        ListNode root = new ListNode(1);
                root.next = root;
        detectCycle(root);
    }
    public static ListNode detectCycle(ListNode head) {
        boolean flag = false;
        ListNode p = head, q = head;
        while (!flag && p != null && p.next != null) {
            if (p.next == q || p.next.next == q) {
                flag = true;
            } else {
                p = p.next.next;
                q = q.next;
            }
        }
        while (flag && head != q) {
            p = q.next;
            while (head != p && p != q) p = p.next;
            if (head == p) {
                return head;
            } else head = head.next;

        }
        return flag?q:null;
    }
}
